1. Field of the Invention
The present invention relates to image processing. In particular, the present invention relates to data compression technology used in a binary representation of an image.
2. Discussion of the Related Art
A binary image is a representation of an image using a two-dimensional array of picture elements ("pixels"), where each pixel is represented by a single bit. Typically, the binary image is seen as constituted by a number of vertically arranged horizontal lines of pixels. Corresponding to this view, the binary image is stored line-by-line, i.e. the pixels in the top-most horizontal line is stored first, followed by the remaining lines in the order of their vertical positions. Such a binary image is typically used in a facsimile transmission or in a laser printer. Because of redundancy in an image, a binary image is often compressed to a more compact format to allow the binary image to occupy less storage space or a shorter transmission time. The original one-bit-per-pixel binary image is recovered by a corresponding decompression when required to be rendered for display or print.
One class of methods for compressing binary images in the prior art is the class of dictionary-based compression methods or algorithms. Dictionary-based compression methods include such methods as LZW, LZ77 and LZ78, which are well-known methods in the prior art. In a dictionary-based method, the binary image is read as a bit stream. As the bit stream is read, a "dictionary"--i.e. a collection of bit patterns encountered in the bit stream--is compiled. When a previously encountered bit pattern is seen, a dictionary code identifying an entry in the dictionary corresponding to the bit pattern, rather than the bit pattern itself, is substituted. The dictionary code is almost always represented by a number of bits which is less than the number of bits in the bit pattern the dictionary code identifies. Thus, significant saving in storage space or transmission time is realized, especially in a binary image where repetition of bit patterns occur frequently. Programs implementing dictionary-based compressions are readily available. For example, a utility program, called "compress", for performing a dictionary-based compression on a UNIX data file is released with many implementations of the UNIX operating system.
In the dictionary-based compression method described above, because the image is read as bit patterns in a sequence of horizontal lines, only redundancy in the bit patterns along the horizontal direction is exploited. Most binary images, however, possess redundancy in the vertical direction as well. Hence, the present invention described below exploits redundancy in both the vertical and horizontal directions effectively to accomplish a statistically higher level of compression not achieved in the prior art.